package lesson01;

import java.util.Random;

public class SortSelect {

    /**
     * 交换数组位置的值
     * @param arr
     * @param o
     * @param v
     */
    static void swap(int[] arr, int o, int v){
        int temp = arr[o];
        arr[o] = arr[v];
        arr[v] = temp;
    }

    // 选择排序
    static void selectSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                minIndex = arr[minIndex]>arr[j] ? j : minIndex;
                swap(arr,i,minIndex);
            }
        }
    }

    // 冒泡排序
    static void  bubbleSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        int  N = arr.length-1;
        for (int end = N; end >= 0; end--) {
            // 0,1  1,2  2,3 .... N-1,N
            for (int j = 1; j <= N; j++) {
                if(arr[j]<arr[j-1]){
                    swap(arr,j-1,j);
                }
            }
        }
    }

    // 插入排序
    static void insertSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        // 0~0,   0~1,  0~2[0~1], 0~3[0~2,0~1]
        int N =  arr.length;
        for (int i = 1; i < N; i++) {
            for (int j = i; j > 0  ; j--) {
                if(arr[j] > arr[j-1]) break;
                swap(arr, j-1, j);
            }
            // 用 while 实现
        }
    }

    static void print(int[] arr){
        for(int i: arr ){
            System.out.print(i+",");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Random random = new Random();
        int[] arr = new int[10];
        for (int i = 0; i < 9; i++) {
            arr[i] = random.nextInt(10); // (int)(Math.random()*10); //random.nextInt(10);
        }
        System.out.print("排序前：");
        print(arr);
        //selectSort(arr);
        //bubbleSort(arr);
        insertSort(arr);
        System.out.print("排序后：");
        print(arr);
    }
}
